package 排序算法.桶排序;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @Project: data-structure-and-algorithms
 * @Package: 排序.桶排序
 * @ClassName: BucketSort
 * @Author: zhouyihe
 * @Date: 2025/11/17 10:40
 * @Description: 桶排序
 */
public class BucketSort {

    private static void bucketSort(double[] arr) {
        if (arr.length < 1) {
            return;
        }

        // 确定桶的数量
        int bucketCount = arr.length;

        // 创建桶
        List<List<Double>> buckets = new ArrayList<>(bucketCount);
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }

        double min = arr[0], max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
            if (arr[i] < min) {
                min = arr[i];
            }
        }

        // 计算每个桶的大小
        double range = (max - min) / bucketCount;

        // 将元素分配到对应的桶中
        for (double item : arr) {
            // 计算元素应该放入哪个桶
            int bucketIndex = (int) ((item - min) / range);

            // 处理最大值的边界情况
            if (bucketIndex == bucketCount) {
                bucketIndex--;
            }

            buckets.get(bucketIndex).add(item);
        }

        // 对每个桶中的元素进行排序
        for (List<Double> bucket : buckets) {
            Collections.sort(bucket);
        }

        // 将桶中排序好的元素放回原数组
        int index = 0;
        for (List<Double> bucket : buckets) {
            for (double item : bucket) {
                arr[index++] = item;
            }
        }

    }


    // 计数器和测试法
    // for test
    public static void main(String[] args) {
        double[] arr = {0.13, 0.24, 0.32, 0.38, 0.42, 0.56, 0.65, 0.73, 0.85, 0.91};
        bucketSort(arr);
        System.out.println(Arrays.toString(arr));
    }


}
